938D - Buy a Ticket - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
typedef pair<ll, ll> p;
priority_queue<p> q;
const int N = 2e5 + 1;
ll i, v, u, w, n, m, a[N], mn[N], V[N];
vector<p> G[N];

int main() {
    cin >> n >> m;
    for (i = 0; i < m; ++i)
        cin >> v >> u >> w, G[v].push_back({u, -w * 2}), G[u].push_back({v, -w * 2});
    for (i = 1; i <= n; ++i) cin >> w, q.push({-w, i});
    while (!q.empty()) {
        auto [c, x] = q.top();
        q.pop();
        if (V[x]) continue;
        mn[x] = c, V[x] = 1;
        for (auto &[y, d]: G[x]) q.push({c + d, y});
    }
    for (i = 1; i <= n; ++i) cout << -mn[i] << ' ';
    cout << '\n';
}

/* Sat Feb 18 2023 18:46:58 GMT+0300 (Moscow Standard Time) */